import javax.swing.*;
import java.awt.print.Book;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    List<String> list=new ArrayList<>();
    public String[] permutation(String S) {
        char[] ch=S.toCharArray();
        Arrays.sort(ch);
        boolean[] booleans=new boolean[ch.length];
        StringBuilder sb=new StringBuilder();
        dfs(ch,sb,booleans);
        return list.toArray(new String[0]);
    }
    public void dfs(char[] ch, StringBuilder sb, boolean[] booleans){
        if(sb.length()==ch.length){
            list.add(sb.toString());
            return ;
        }
        for(int i=0;i<ch.length;i++){
            if(booleans[i]){
                continue;
            }
            if(i>0&&!booleans[i-1]&&ch[i]==ch[i-1]){
                continue;
            }
            booleans[i]=true;
            sb.append(ch[i]);
            dfs(ch,sb,booleans);
            booleans[i]=false;
            sb.deleteCharAt(sb.length()-1);
        }
    }













    int ret=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null){
            return 0;
        }
        dfs1(root);
        return ret;
    }
    public int dfs1(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=Math.max(0,dfs1(root.left));
        int right=Math.max(0,dfs1(root.right));
        int sum=left+right+root.val;
        ret=Math.max(ret,sum);
        return root.val+Math.max(left,right);
    }














    int max=Integer.MIN_VALUE;
    public int maxPathSum1(TreeNode root) {
        if(root==null){
            return 0;
        }
        maxdfs(root);
        return max;
    }
    public int maxdfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=Math.max(0,maxdfs(root.left));
        int right=Math.max(0,maxdfs(root.right));
        int sum=root.val+left+right;
        max=Math.max(max,sum);
        return root.val+Math.max(left,right);
    }
















    public boolean isInterleave(String s1, String s2, String s3) {
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();
        if(len1+len2!=len3){
            return false;
        }
        boolean[] booleans=new boolean[len2+1];
        booleans[0]=true;
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                int p=i+j-1;
                if(i>0){
                    booleans[j]=booleans[j]&&s1.charAt(i-1)==s3.charAt(p);
                }
                if(j>0){
                    booleans[j]=booleans[j]||(booleans[j-1]&&s2.charAt(j-1)==s3.charAt(p));
                }
            }
        }
        return booleans[len2];
    }














    public boolean isInterleave1(String s1, String s2, String s3) {
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();
        if(len1+len2!=len3){
            return false;
        }
        boolean[] booleans=new boolean[len2+1];
        booleans[0]=true;
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                int p=i+j-1;
                if(i>0){
                    booleans[j]=booleans[j]&&s1.charAt(i-1)==s3.charAt(p);
                }
                if(j>0){
                    booleans[j]=booleans[j]||(booleans[j-1]&&s2.charAt(j-1)==s3.charAt(p));
                }
            }
        }
        return booleans[len2];
    }













    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack=new Stack<>();
        int i=0;
        while(i<asteroids.length){
            if(stack.isEmpty()||stack.peek()<0||asteroids[i]>0){
                stack.push(asteroids[i]);
            }else if(stack.peek()<=-asteroids[i]){
                if(stack.pop()<-asteroids[i]){
                    continue;
                }
            }
            i++;
        }
        int[] arr=new int[stack.size()];
        for(int j=stack.size()-1;j>=0;j--){
            arr[j]=stack.pop();
        }
        return arr;
    }













        public int[] asteroidCollision1(int[] asteroids) {
            Stack<Integer> stack=new Stack<>();
            int i=0;
            while(i<asteroids.length){
                if(stack.isEmpty()||stack.peek()<0||asteroids[i]>0){
                    stack.push(asteroids[i]);
                }else if(stack.peek()<=-asteroids[i]){
                    if(stack.pop()<-asteroids[i]){
                        continue;
                    }
                }
                i++;
            }
            int[] arr=new int[stack.size()];
            for(int j=stack.size()-1;j>=0;j--){
                arr[j]=stack.pop();
            }
            return arr;
        }













    public int maxProduct(String[] words) {
        int len=words.length;
        int[] arr=new int[len];
        for(int i=0;i<len;i++){
            arr[i]=maxProducts(words[i]);
        }
        int max=0;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if((arr[i]&arr[j])==0){
                    max=Math.max(max,words[i].length()*words[j].length());
                }
            }
        }
        return max;
    }
    public int maxProducts(String str){
        int ans=0;
        for(char ch:str.toCharArray()){
            ans|=1<<(ch-'a');
        }
        return ans;
    }















    public int maxProduct1(String[] words) {
        int len=words.length;
        int[] arr=new int[len];
        for(int i=0;i<len;i++){
            arr[i]=maxProducts1(words[i]);
        }
        int max=0;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if((arr[i] & arr[j])==0){
                    max=Math.max(max,words[i].length()*words[j].length());
                }
            }
        }
        return max;
    }
    public int maxProducts1(String str){
        int ans=0;
        for(char ch : str.toCharArray()){
            ans |= 1<<(ch-'a');
        }
        return ans;
    }
}
